package com.xinxin.leetcode.problem543;

import com.xinxin.leetcode.common.TreeNode;
import com.xinxin.leetcode.common.TreeUtil;

/**
 * @author ShiXinXin
 * @date 2020-01-17 10:05
 */
class Solution {
    int max = 0;

    private int treeHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int right = treeHeight(root.right);
        int left = treeHeight(root.left);
        if (right + left > max) {
            max = right + left;
        }
        return Math.max(right, left) + 1;
    }

    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        treeHeight(root);
        return max;
    }

    public static void main(String[] args) {
        TreeNode root = TreeUtil.createTree(new int[]{1, 2, 4, 0, 0, 5, 0, 0, 3, 0, 0});
        System.out.println(new Solution().diameterOfBinaryTree(root));
    }
}
